package com.example.bfrk32.bfrk;

/**
 * @description
 * @auther lijiewei
 * @date 2021/12/15 10:47
 */
public class Bfrk {

    /**
     * Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法
     * @param a 主串
     * @param b 模式串
     * @return 第一次匹配的起始位置
     * @author lijiewei
     * @date   2021/12/15 10:55
     */
    public static int bf(String a, String b) {
        int m = a.length();
        int n = b.length();
        //多少个字符匹配上了
        int k = 0;
        char[] aArr = a.toCharArray();
        char[] bArr = b.toCharArray();
        for (int i = 0; i < m-n; i++) {
            k = 0;
            for(int j=0; j<n; j++) {
                if(aArr[i+j] == bArr[j]) {
                    k++;
                } else {
                    break;
                }
            }
            if (k == n) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Rabin-Karp 算法
     * @param a 主串
     * @param b 模式串
     * @return
     * @author lijiewei
     * @date   2021/12/15 11:15
     */
    public static int rk(String a, String b) {
        int m = a.length();
        int n = b.length();
        //存放子串的hash 值
        int[] hash = new int[m-n+1];
        //存放26 的次方的值
        int[] table = new int[26];
        char[] aArr = a.toCharArray();
        char[] bArr = b.toCharArray();
        int s = 1;
        int j = 0;
        //将 26 的次方存储在一个表里，取的时候直接用，虽然溢出，但没啥问题
        for (j = 0; j < 26; j++) {
            table[j] = s;
            s = s*26;
        }
        //计算子串 hash 值
        for (int i=0; i<=m-n; i++) {
            s = 0;
            for (j=0; j<n; j++) {
                s+=(aArr[i+j]-'a')*table[n-1-j];
            }
            hash[i]=s;
        }
        s=0;
        //计算模式串hash值
        for(j=0; j<n; j++) {
            s+=(bArr[j]-'a')*table[n-1-j];
        }
        for(j=0; j<m-n+1; j++) {
            if (hash[j] == s) {
                return j;
            }
        }
        return -1;
    }
}
